package com.mz;

import java.util.Stack;

public class BinaryTree {
	protected Node root;

	public BinaryTree(Node root) {
		this.root = root;
	}

	public Node getRoot() {
		return root;
	}

	/** 构造树 */
	public static Node init() {
		Node a = new Node('A');
		Node b = new Node('B', null, a);
		Node c = new Node('C');
		Node d = new Node('D', b, c);
		Node e = new Node('E');
		Node f = new Node('F', e, null);
		Node g = new Node('G', null, f);
		Node h = new Node('H', d, g);
		return h;// root
	}

	/** 访问节点 */
	public static void visit(Node p) {
		System.out.print(p.getKey() + " ");
	}

	/** 递归实现前序遍历 */
	protected static void preorder(Node p) {
		if (p != null) {
			visit(p);
			preorder(p.getLeft());
			preorder(p.getRight());
		}
	}

	/** 递归实现中序遍历 */
	protected static void inorder(Node p) {
		if (p != null) {
			inorder(p.getLeft());
			visit(p);
			inorder(p.getRight());
		}
	}

	/** 递归实现后序遍历 */
	protected static void postorder(Node p) {
		if (p != null) {
			postorder(p.getLeft());
			postorder(p.getRight());
			visit(p);
		}
	}
	
	/** 非递归实现前序遍历 */
	protected static void iterativePreorder(Node p) {
	   Stack<Node> stack = new Stack<Node>();
	   if (p != null) {
	    stack.push(p);
	    while (!stack.empty()) {
	     p = stack.pop();
	     if (p.getRight() != null)
	      stack.push(p.getRight());
	     if (p.getLeft() != null)
	      stack.push(p.getLeft());
	    }
	   }
	}
	
	/** 非递归实现前序遍历2 */
	protected static void iterativePreorder2(Node p) {
	   Stack<Node> stack = new Stack<Node>();
	   Node node = p;
	   while (node != null || stack.size() > 0) {
	    while (node != null) {//压入所有的左节点，压入前访问它
	     visit(node);
	     stack.push(node);
	     node = node.getLeft();
	    }
	    if (stack.size() > 0) {//
	     node = stack.pop();
	     node = node.getRight();
	    }
	   }
	}
	public static void main(String[] args) {
		
		   BinaryTree tree = new BinaryTree(init());
		   System.out.print("前 Pre-Order:");
		   preorder(tree.getRoot());
		   System.out.println();
		   System.out.print("中 In-Order:");
		   inorder(tree.getRoot());
		   System.out.println();
		   System.out.print("后  Post-Order:");
		   postorder(tree.getRoot());
		   System.out.println();
		   System.out.print(" Pre-Order:");
		   //iterativePreorder(tree.getRoot());
		   System.out.println();
		   System.out.print("Pre-Order2:");
		   //iterativePreorder2(tree.getRoot());

		}

}

